package src.dp.entire_bag;

public class no322 {//零钱兑换

    /**
     * 1. dp数组下标含义：装满容量 j 的背包，最少需要 dp[j] 件物品
     * 2. 递推公式：dp[j] = Math.min(dp[j], dp[j - coins[i]] +1 )
     * 3. 初始化数组：因为每次取 min，所以要初始化为一个大的数 INT_MAX, dp[0]=0
     * 4. 遍历顺序：coins（物品）放在外循环，amount（背包）在内循环。且内循环正序
     */
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        //凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;
        dp[0] = 0;
        //初始化dp数组为很大的数
        for (int i = 1; i < dp.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                //只有dp[j-coins[i]]不是初始最大值时，该位才有选择的必要
                if (dp[j - coins[i]] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];

    }

}
